from pprint import pprint

import numpy as np


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


# 欧拉筛：筛选出<=x的所有素数，prime是筛选出的素数列表，f为bool数组，f[t]==0表示t为素数，否则不是
def euler_prime(x):
    s = 0
    f = np.zeros(x + 1)
    prime = []
    for i in range(2, x):
        if f[i] == 0:
            prime.append(i)
        for j in range(len(prime)):
            if i * prime[j] > x:
                break
            f[i * prime[j]] = 1
            if i % prime[j] == 0:
                break
    f[0] = f[1] = 1
    for i in range(len(f)):
        if f[i] == 0:
            f[i] = 1
        else:
            f[i] = 0
    return prime, f


# 根据试验次数n，返回均匀试验表最多能构建的列数
def get_max_column(n):
    assert n >= 3, '试验数应不少于3'
    prime_list, is_prime = euler_prime(n)
    # print(prime_list)
    # print(is_prime)
    if is_prime[n]:
        return n - 1
    ans = n
    for p in prime_list:
        if n % p == 0:
            ans -= ans / p
        while n % p == 0:
            n /= p
        if n == 1:
            break

    print('试验数为%d时，生成的均匀设计表最多支持%d个因素' % (len(is_prime)-1, int(ans)))
    return int(ans)


# 根据水平数获取均匀设计表，print_info为一个bool变量，为True时打印表信息
# 复杂度O(nlogn)
def uniform_design(level, print_info=True):
    n = level
    res = []
    arr = []
    for i in range(n):
        if gcd(i, level) == 1:
            arr.append(i)
    res.append(arr)

    tmp = []
    for i in range(1, n):
        for j in arr:
            num = j * (i + 1) % n
            tmp.append(num if num != 0 else n)
        res.append(tmp)
        tmp = []

    if print_info:
        print('已生成%d水平均匀设计表' % level)
        print('该表共有%d行，即需要进行%d试验' % (level, level))
        print('该表共有%d列，最多支持%d个因子的试验' % (len(arr), len(arr)))
        print('以下为该均匀设计表的使用表')
        print('....')
        print('其余功能正在完善')
    return res


def uniform_design_star(level):
    res = uniform_design(level + 1, print_info=False)
    res.pop()
    return res


if __name__ == '__main__':
    res = uniform_design(6)
    pprint(res)
    pprint(uniform_design(7))
    res = uniform_design_star(6)
    pprint(res)

    get_max_column(18)
